#include <iostream>
#include <vector>

int rod_cutting_topdown(const std::vector<int>& p, int n, std::vector<int> & r, std::vector<int> & s) //r[n] >= 0 after first computation
{
	if (r[n] >= 0)
		return r[n];
	if(n<=0)
		return 0;
	int q = -1; //return value
	for (int i = 1; i <=n; i++) {
		int remainder = rod_cutting_topdown(p,n-i,r,s);
		if ( q < p[i] + remainder ) {
			q = p[i] + remainder;
			s[n] = i;
		}

	}
	r[n] = q;
	return q;
}

int rod_cutting_bottomup(const std::vector<int> & p, int n, std::vector<int> & r, std::vector<int> & s) {
	r[0] = p[0];
	r[1] = p[1];
	for ( int i = 2; i <= n ; i++) {
		int q = -1;
		for (int j = 1; j <= i; j++) {
			if (q < p[j] + r[i-j]) {
				q = p[j] + r[i-j];
				s[i] = j;
			}
		}
		r[i] = q;
	}
	return r[n];
}


void init_p(std::vector<int> & p) {
	int a[11] = {0,1,5,8,9,10,17,17,20,24,30};
	for (int i = 0; i < 11; ++i)
		p[i] = a[i];
}

void init_r(std::vector<int> & r) {
	for (int i = 0; i < 11; ++i)
		r[i] = -1;
}

void init_s(std::vector<int> & s) {
	for (int i = 0; i < 11; ++i)
		s[i] = -1;
}

void print_solution(int n, const std::vector<int> & s) {
	while(n>0) {
		std::cout << s[n] << " : ";
		n -= s[n];
	}
	std::cout << std::endl;
}
void reset(std::vector<int> & p, std::vector<int> & r, std::vector<int> & s) {
	init_p(p); 
	init_r(r);
	init_s(s);
}

void test_rod_cutting() {
	std::vector<int> p(11);
	std::vector<int> r(11);
	std::vector<int> s(11);
	reset(p,r,s);

	int n;
	while (true) {
		std::cin >> n;
		if(n<0)
			break;
		reset(p,r,s);
		std::cout << "optimal solution(top-down) is " << rod_cutting_topdown(p,n,r,s) << std::endl;
		print_solution(n,s);

		reset(p,r,s);
		std::cout << "optimal solution(bottom-up) is " << rod_cutting_topdown(p,n,r,s) << std::endl;
		print_solution(n,s);
	}
}